import DFS.BipartionDetection;
import DFS.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class HungarianDFS {
    private Graph graph;
    private int maxMatching = 0;
    private int[] matching;
    private boolean[] visited;

    public HungarianDFS(Graph g) {
        BipartionDetection bd = new BipartionDetection(g);
        if (!bd.isBipartite()) {
            throw new IllegalArgumentException("Hungarian only works for bipartion graph.");
        }
        this.graph = g;
        int[] colors = bd.colors();
        matching = new int[g.getVertexNum()];
        Arrays.fill(matching, -1);
        visited = new boolean[g.getVertexNum()];
        for (int v = 0; v < g.getVertexNum(); v++) {
            if (colors[v] == 0 && matching[v] == -1) {
                Arrays.fill(visited, false);
                if (dfs(v)) {
                    maxMatching++;
                }
            }
        }
    }

    public boolean dfs(int v) {
        visited[v] = true;
        for (int u : graph.adj(v)) {
            if (!visited[u]) {
                visited[u] = true;
                if (matching[u] == -1 || dfs(matching[u])) {
                    matching[v] = u;
                    matching[u] = v;
                    return true;
                }
            }
        }
        return false;
    }


    public int maxMatching() {
        return maxMatching;
    }

    public boolean isPerfectMatching() {
        return maxMatching * 2 == graph.getVertexNum();
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        HungarianDFS hungarian = new HungarianDFS(g);
        System.out.println(hungarian.maxMatching);
    }
}
